//
// Created by user on 2022/4/25.
//
#include <vector>
#include <algorithm>
using namespace std;
/*
    0 - 1 背包：
        有 n 种物品和一个容量为 C 的背包，
        第 i 件物品的重量是 w[i]，价值是 v[i]，件数是 1 件
        求将哪些物品装入背包可使得价值总和最大
 */
class Knapsack{
public:
    vector<int> &w;
    vector<int> &v;
    int maxValue=0;

    //DFS 前序遍历
    int knapsack(vector<int> &w, vector<int> &v, int C){
        this->w = w;
        this->v = v;
        dfs(0, C, 0);
        return maxValue;
    }

    void dfs(int index, int c, int currValue){
        //处理当前节点
        maxValue = max(maxValue, currValue);
        for (int i = index; i <w.size() ; ++i) {
            int childIndex =i +1;
            if(childIndex==w.size())continue;
            if(c<w[childIndex])continue;

            dfs(childIndex, c-w[childIndex], currValue+v[childIndex]);
        }
    }

    //DFS 后序遍历
    int knapsack1(vector<int> &w, vector<int> &v, int C){
        this->w = w;
        this->v = v;

        return dfs(0, 0);;
    }

    int dfs(int index, int c){

        int maxValue=0;
        //从index开始是为了控制顺序
        for (int i = index; i < w.size(); ++i) {
            int childIndex = i+1;

            if (childIndex==w.size())continue;
            if(c<w[childIndex])continue;
            int value = dfs(childIndex, c-w[childIndex]);
            maxValue = max(maxValue, value);
        }
        return maxValue+index==-1?0:v[index];
    }

    //动态规划
    ///dp[i][c]：将[0..i]号物品放入容量为c的背包中产生的最大价值
    //状态转移矩阵 1） 不放 d[i][c] = dp[i-1][c]  c<w[i]   2）放 dp[i][c] = max(dp[i-1][c], v[i]+dp[i-1][c-w[i]]) c>=w[i]
    int knapsack2(vector<int> &w, vector<int> &v, int C){
        //状态维度定义
        vector<vector<int>> dp(w.size(),vector<int>(v.size()+1));

        //状态初始化
        dp[0][0] = 0;
        //考虑将第0号物品放背包中
        for (int i = 0; i < w.size(); ++i) {
            for (int c = 0; c <=C ; ++c) {
                if(c<w[i]){
                    dp[i][c] = dp[i-1][c];
                }else{
                    dp[i][c] = max(dp[i-1][c], v[i]+dp[i-1][c-w[i]]);
                }
            }
        }
        return dp[w.size()-1][C];
    }

    //动态规划+空间压缩
    ///dp[i][c]：将[0..i]号物品放入容量为c的背包中产生的最大价值
    //状态转移矩阵 1） 不放 d[i][c] = dp[i-1][c]  c<w[i]   2）放 dp[i][c] = max(dp[i-1][c], v[i]+dp[i-1][c-w[i]]) c>=w[i]
    int knapsack3(vector<int> &w, vector<int> &v, int C){
        //状态维度定义
        vector<int> dp(v.size()+1);

        //状态初始化
        dp[0] = 0;
        //考虑将第0号物品放背包中
        for (int i = 0; i < w.size(); ++i) {
            for (int c = C; c >=w[i] ; c--) {
               dp[c] = max(dp[c], v[i]+dp[c-w[i]]);
            }
        }
        return dp[C];
    }
};